package com.lwx.algorithm.chapter6;

import java.util.*;

public class Offer347 {
    public static void main(String[] args) {
        Offer347 o = new Offer347();
        int nums[] = {1,1,1,2,2,3};
        int k = 2;
        int[] ret = o.topKFrequent(nums, k);
        System.out.println(Arrays.toString(ret));
    }

    public int[] topKFrequent(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return null;
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer num = map.get(nums[i]);
            if(Objects.isNull(num)){
                map.put(nums[i],1);
            }else {
                map.put(nums[i],num+1);
            }
        }
        PriorityQueue<Pair> queue = new PriorityQueue<>(map.size(), new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o2.getValue() - o1.getValue();
            }
        });

        Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry<Integer, Integer> entry = iterator.next();
            Pair pair = new Pair();
            pair.setKey(entry.getKey());
            pair.setValue(entry.getValue());
            queue.offer(pair);
        }
        int[] ret = new int[k];
        if(k<=map.size()){
            for (int i = 0; i < k; i++) {
                ret[i] = queue.poll().getKey();
            }
        }else {
            for (int i = 0; i < k; i++) {
                ret[i] = queue.poll().getKey();
            }
        }
        return ret;

    }

    class Pair{
        private int key;
        private int value;

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }
    }
}
